package com.mc.string;

/**
 * BM 算法进行字符串匹配，左对齐，但是从右向左进行匹配，当匹配失败时，通过匹配串中失败的字符查找辅助数组中的偏移量，进而更新匹配位置
 *
 * @author MC
 *
 */
public class BM {
	
	private int[] right;
	private String pattern;
	public BM(String pattern){
		this.pattern = pattern;
		right = new int[256];//ASCII扩展字符集
		for(int i=0;i<256;i++)
			right[i]=-1;
		for(int j=0;j<pattern.length();j++)
			right[pattern.charAt(j)] = j;
	}
	
	public int search(String text){
		int n = text.length();
		int m = pattern.length();
		int skip;
		for(int i=0;i<=n-m;i+=skip){
			skip=0;
			for(int j=m-1;j>=0;j--){
				if(text.charAt(i+j)!=pattern.charAt(j)){
					skip = j-right[text.charAt(i+j)];
					if(skip<0)skip=1;
					break;
				}
			}
			if(skip==0) return i;
		}
		return n;
	}
}	
